package it.storm.solution;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 950. 按递增顺序显示卡牌
 * https://leetcode-cn.com/problems/reveal-cards-in-increasing-order/
 */
public class Solutions_950 {
    public static void main(String[] args) {
        int[] deck = {17, 13, 11, 2, 3, 5, 7};  // output: {2, 13, 3, 11, 5, 17, 7}
        int[] result = deckRevealedIncreasing(deck);

        System.out.println(Arrays.toString(result));
    }

    public static int[] deckRevealedIncreasing(int[] deck) {
        if (deck == null) {
            return new int[0];
        }
        Arrays.sort(deck);
        int len = deck.length;
        int[] res = new int[len];
        LinkedList<Integer> queue = new LinkedList<>();
        // 模拟过程（数组 deck 有序的情况下）
        // 1. 较大的牌入队
        // 2. 队尾元素移动到队头
        // 3. 当前遍历元素，再添加到队头
        for (int i = len - 1; i >= 0; i--) {
            if (!queue.isEmpty()) {
                queue.addFirst(queue.pollLast());
            }
            queue.addFirst(deck[i]);
        }
        for (int i = 0; i < len; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}
